#ifndef _COMMON_HPP_
#define _COMMON_HPP_
#include <vector>
#include <unordered_map>
#include <deque>
#include <algorithm>
#include <string>
#include <iostream>
#include <climits>

using namespace ::std;

// List related structure and function
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* makeVecToList(vector<int>& value);
vector<int> makeListToVec(ListNode* head);
ListNode* makeCycleLinkedList(vector<int>& value, int pos);
ListNode* getCrossPoint(ListNode *head, int pos); // 获取环形链表中的交叉点


// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
TreeNode* makeVectorToBinaryTree(vector<int>& vec);
vector<int> makeBinaryTreeToVector(TreeNode* root);

// common function
vector<int> makeArrayToVector(int array[], int size);
void printVector(vector<int>& out);

vector<int> makeArrayToVector(int array[], int size) {
    vector<int> vec = {};
    for(int i = 0; i < size; ++i) {
        vec.push_back(array[i]);
    }
    return vec;
}

// ListNode* makeVecToList(vector<int>& value) {
//     ListNode *head = nullptr, *cur, *next;
//     if(value.empty()) return head;
//     head = cur = (ListNode*)malloc(sizeof(ListNode));
//     cur->val = value[0]; cur->next = nullptr;
//     for(int i = 1; i < value.size(); ++i) {
//         next = (ListNode*)malloc(sizeof(ListNode));
//         next->val = value[i]; next->next = nullptr;
//         cur->next = next; cur = next;
//     }
//     return head;
// }

ListNode* makeVecToList(vector<int>& value) {
    ListNode *head = nullptr, *cur, *next;
    if(value.empty()) return head;
    head = cur = new ListNode(value[0], nullptr);
    for(int i = 1; i < value.size(); ++i) {
        next = new ListNode(value[i], nullptr);
        cur->next = next; cur = next;
    }
    return head;
}

vector<int> makeListToVec(ListNode* head) {
    vector<int> value;
    while(head != nullptr) {
        value.push_back(head->val);
        head = head->next;
    }
    return value;
}

ListNode* makeCycleLinkedList(vector<int>& value, int pos) {
    if(value.empty()) return nullptr;
    ListNode *head, *cur, *cyclePoint;
    head = cur = new ListNode(value[0]);
    if(0 == pos) cyclePoint = cur;
    for(int i = 1; i < value.size(); ++i) {
        ListNode* next = new ListNode(value[i], nullptr);
        cur->next = next; cur = next;
        if(i == pos) cyclePoint = cur;
    }
    if(pos != -1) cur->next = cyclePoint;
    return head;
}

ListNode* getCrossPoint(ListNode *head, int pos) {
    for(int i = 0; i < pos; ++i) {
        head = head->next;
    }
    return head;
}



TreeNode* makeVectorToBinaryTree(vector<int>& vec) {
    if(vec.empty()) return nullptr;
    TreeNode* root = new TreeNode(vec[0]);
    deque<TreeNode*> que;
    que.push_back(root);
    int index = 1;
    while(index < vec.size()) {
        TreeNode* cursor = que.front();
        que.pop_front();
        if(vec[index] != INT_MAX) {
            cursor->left = new TreeNode(vec[index]);
            que.push_back(cursor->left);
        } else {
            cursor->left = nullptr;
        }
        // cursor->left = (vec[index] == INT_MAX ? nullptr : new TreeNode(vec[index])); // 这样会报段错误，为什么？
        // if(cursor->left != nullptr) que.push_back(cursor->left);
        index++;
        if(index == vec.size()) break;

        if(vec[index] != INT_MAX) {
            cursor->right = new TreeNode(vec[index]);
            que.push_back(cursor->right);
        } else {
            cursor->right = nullptr;
        }
        // cursor->right = (vec[index] == INT_MAX ? nullptr : new TreeNode(vec[index]));
        // if(cursor->left != nullptr) que.push_back(cursor->left);
        index++;
    }
    return root;
}

vector<int> makeBinaryTreeToVector(TreeNode* root) {
    if(nullptr == root) return {};
    vector<int> vec;
    deque<TreeNode*> que;
    vec.push_back(root->val);
    que.push_back(root);
    while(!que.empty()) {
        TreeNode* cursor = que.front();
        que.pop_front();

        if(cursor->left) {
            que.push_back(cursor->left);
            vec.push_back(cursor->left->val);
        } else {
            vec.push_back(INT_MAX);
        }
        if(cursor->right) {
            que.push_back(cursor->right);
            vec.push_back(cursor->right->val);
        } else {
            vec.push_back(INT_MAX);
        }
    }

    for(vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend() && *it == INT_MAX; ++it) {
        vec.pop_back();
    }
    return vec;
}



// printVector(tasks);
// or printVector<char>(tasks);
template <typename T = int>
void printVector(vector<T>& out) {
    // cbegin() 返回 const_iterator，访问时不可以改变元素的值 Container<T>::const_iterator
    // for (auto it = out.cbegin(); it != out.cend() ; ++it) cout << *it << " "; cout << endl;
    for_each(out.begin(), out.end(), [=](T x) { cout << x << " "; });
    cout << endl;
}

#endif